package com.rgs.se.algorithm.recursive;

/*
    递归思想：我解决一部分，剩下的交给递归完成
    1.求阶乘
 * 2.打印i-j
 * 3.数组求和
 * 4.反转字符串
 * 5.斐波那契数列
 * 6.最大公约数
 * 7.排序该递归
 * 8.汉罗塔*/
public class Test1 {
    

    //1.求阶乘
    static int f1(int n){
        if(n == 1){
            return 1;
        }
        return n*f1(n-1);
    }
    //2.打印i-j
    static void f2(int i,int j){
        if(i > j){
            return;
        }
        System.out.println(i);
        f2(i+1,j);
    }
    //3.数组求和
    static int f3(int[] arr,int begin){
        if(begin == arr.length-1){
            return arr[begin];
        }
        return arr[begin]+f3(arr,begin+1);

    }
    //4.反转字符串
    static String f4(String s,int end){
        if (end == 0){
            return ""+s.charAt(0);
        }
        return s.charAt(end) + f4(s,end-1);
    }
    //5.斐波那契数列
    static int f5(int n){
        if (n == 1 || n == 2){
            return 1;
        }
        return f5(n-1)+f5(n-2);
    }
    //6.最大公约数
    static int gcd(int m,int n){
        if(n == 0) return m;
        return gcd(n,m%n);
    }
    // 7.排序该递归
    static void insertSort(int[] arr,int k){
        if(k == 0){
            return;
        }
        //对前k-1个元素排序
        insertSort(arr,k-1);
        int x = arr[k];
        int index = k-1;
        while (index > -1 && x < arr[index]){
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = x;
    }
    //8.汉罗塔
    static void printHanoiTower(int N,String from,String to,String help){
        if(N == 1){
            System.out.println("move "+N+" from "+from+" to "+to);
            return;
        }
        printHanoiTower(N-1,from,help,to);//先把前N-1个盘子放到辅助空间上
        System.out.println("move "+N+" from "+from+" to "+to);//N可以顺利到达targe
        printHanoiTower(N-1,help,to,from);//让N-1从辅助空间到源空间
    }
    //9.二分查找
    static int binarySearch1(int[] arr,int left,int right,int key){
        if(left > right){
            return -1;
        }
        int mid = (left+right)/2;
        if (key < arr[mid]){
            return binarySearch1(arr,left,mid,key);
        }
        else if(key > arr[mid]){
            return binarySearch1(arr,mid+1,right,key);
        }else {
            return mid;
        }
    }
    //去重
    static int removalArray(int[] arr){
        int slow = 0,fast = 1;
        int n = arr.length;
        while(fast < n){
            if (arr[fast] != arr[slow]){
                slow++;
                arr[slow] = arr[fast];
            }
            fast++;
        }
        for (int i = 0; i < slow+1; i++) {
            System.out.println(arr[i]);
        }
        System.out.println();
        return slow+1;
    }

    public static void main(String[] args) {
        //System.out.println(f1(3));
        //f2(1,10);
//          int []arr = {9,2,3,4,1,6,7,8,5};
//        System.out.println(f3(arr,0));
//        String s = "abcd";
//        System.out.println(f4(s,3));
//        System.out.println(f5(5));
//        insertSort(arr,9);
//        printHanoiTower(5,"Subject1","B","C");
//
        int[] arr1 = {1,2,2,3,4,6,6,6,7,8,9,9};
        System.out.println(removalArray(arr1));

    }
}
